package com.ljy.my_study.leetcode.公交路线;

import com.ljy.my_study.util.ArrayUtil;

import java.util.*;

public class TestMain {

//    给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
//
//    例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
//    现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
//
//    求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
//
//             
//
//    示例 1：
//
//    输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
//    输出：2
//    解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
//    示例 2：
//
//    输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
//    输出：-1
//             
//
//    提示：
//
//            1 <= routes.length <= 500.
//            1 <= routes[i].length <= 105
//    routes[i] 中的所有值 互不相同
//    sum(routes[i].length) <= 105
//            0 <= routes[i][j] < 106
//            0 <= source, target < 106
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/bus-routes
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        int[][] routes= ArrayUtil.changeStr2Array("[[1,2,7],[3,6,7]]");
        System.out.println(new TestMain().numBusesToDestination(routes,1,6));
        routes= ArrayUtil.changeStr2Array("[[7,12],[4,5,15],[6],[15,19],[9,12,13]]");
        System.out.println(new TestMain().numBusesToDestination(routes,15,12));
    }

    /**
     * 将站牌当成key，bus路线当成value 集群。记录路线与路线之间是否能切换为二维数组中。通过bfs，遍历起始路线到各个路线所需要的切换数量。最终获取目的站点所最少的切换数量
     * @param routes
     * @param source
     * @param target
     * @return
     */
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if(source==target){
            return 0;
        }
        int len=routes.length;
        Map<Integer,List<Integer>> map=new HashMap<>();
        for(int i=0;i<routes.length;i++){
            for(int j=0;j<routes[i].length;j++){
                int key=routes[i][j];
                List<Integer> list= map.getOrDefault(key,new ArrayList<>());
                list.add(i);
                map.put(key,list);
            }
        }
        boolean[][] edge=new boolean[len][len];
        for(Integer key:map.keySet()){
            List<Integer> list= map.getOrDefault(key,new ArrayList<>());
            for(int i=0;i<list.size();i++){
                int a=list.get(i);
                for(int j=i+1;j<list.size();j++){
                    int b=list.get(j);
                    edge[a][b]=edge[b][a]=true;
                }
            }
        }
        int[] array=new int[len];
        Arrays.fill(array,-1);
        Queue<Integer> queue=new LinkedList<>();
        for(Integer i:map.getOrDefault(source,new ArrayList<>())){
            queue.offer(i);
            array[i]=1;
        }
        while(!queue.isEmpty()){
            int i=queue.poll();
            for(int j=0;j<edge[i].length;j++){
                if(edge[i][j]&&array[j]==-1){
                    array[j]=array[i]+1;
                    queue.offer(j);
                }
            }
        }
        int result=Integer.MAX_VALUE;
        for(int i:map.getOrDefault(target,new ArrayList<>())){
            if(array[i]!=-1){
                result=Math.min(array[i],result);
            }
        }
        return result==Integer.MAX_VALUE?-1:result;
    }

}
